import collections


# class Solution(object):
#     def findOrder(self, numCourses, prerequisites):
#         """
#         :type numCourses: int
#         :type prerequisites: List[List[int]]
#         :rtype: List[int]
#         """
#         return_list = []
#         p = collections.defaultdict(list)
#         p_collect = {}
#         stack = collections.deque()
#         for item in prerequisites:
#             p[item[0]].append(item[1])
#             if item[0] not in p_collect:
#                 p_collect[item[0]] = 0
#             if item[1] not in p_collect:
#                 p_collect[item[1]] = 1
#             else:
#                 p_collect[item[1]] += 1
#         for i in range(numCourses):
#             if i not in p_collect:
#                 return_list.append(i)
#             else:
#                 if p_collect[i] == 0:
#                     stack.append(i)
#         while stack:
#             k = stack.popleft()
#             return_list.append(k)
#             if k in p:
#                 for item in p[k]:
#                     p_collect[item] -= 1
#                     if p_collect[item] == 0:
#                         stack.append(item)
#         for key in p_collect:
#             if p_collect[key] > 0:
#                 return []
#         return_list.reverse()
#         return return_list

class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        visited = [0] * numCourses
        p = collections.defaultdict(list)
        for item in prerequisites:
            p[item[0]].append(item[1])
            visited[item[0]] = 1
        return_list = []
        for i in range(numCourses):
            if visited[i] == 0:
                return_list.append(i)

        def dfs(i):
            visited[i] = 2
            for item in p[i]:
                if visited[item] == 2:
                    return False
                if visited[item] == 1:
                    flag = dfs(item)
                    if not flag:
                        return False
            visited[i] = 0
            return_list.append(i)
            return True

        for i in range(numCourses):
            if visited[i] == 1:
                flag = dfs(i)
                if not flag:
                    return []

        return return_list


data = Solution()
numCourses = 3
prerequisites = [[1, 0], [2, 0], [0, 2]]
print(data.findOrder(numCourses, prerequisites))
numCourses = 5
prerequisites = [[1, 4], [2, 4], [3, 1], [3, 2]]
print(data.findOrder(numCourses, prerequisites))
numCourses = 100
prerequisites = [[1, 0], [2, 0], [2, 1], [3, 1], [3, 2], [4, 2], [4, 3], [5, 3], [5, 4], [6, 4], [6, 5], [7, 5], [7, 6],
                 [8, 6], [8, 7], [9, 7], [9, 8], [10, 8], [10, 9], [11, 9], [11, 10], [12, 10], [12, 11], [13, 11],
                 [13, 12], [14, 12], [14, 13], [15, 13], [15, 14], [16, 14], [16, 15], [17, 15], [17, 16], [18, 16],
                 [18, 17], [19, 17], [19, 18], [20, 18], [20, 19], [21, 19], [21, 20], [22, 20], [22, 21], [23, 21],
                 [23, 22], [24, 22], [24, 23], [25, 23], [25, 24], [26, 24], [26, 25], [27, 25], [27, 26], [28, 26],
                 [28, 27], [29, 27], [29, 28], [30, 28], [30, 29], [31, 29], [31, 30], [32, 30], [32, 31], [33, 31],
                 [33, 32], [34, 32], [34, 33], [35, 33], [35, 34], [36, 34], [36, 35], [37, 35], [37, 36], [38, 36],
                 [38, 37], [39, 37], [39, 38], [40, 38], [40, 39], [41, 39], [41, 40], [42, 40], [42, 41], [43, 41],
                 [43, 42], [44, 42], [44, 43], [45, 43], [45, 44], [46, 44], [46, 45], [47, 45], [47, 46], [48, 46],
                 [48, 47], [49, 47], [49, 48], [50, 48], [50, 49], [51, 49], [51, 50], [52, 50], [52, 51], [53, 51],
                 [53, 52], [54, 52], [54, 53], [55, 53], [55, 54], [56, 54], [56, 55], [57, 55], [57, 56], [58, 56],
                 [58, 57], [59, 57], [59, 58], [60, 58], [60, 59], [61, 59], [61, 60], [62, 60], [62, 61], [63, 61],
                 [63, 62], [64, 62], [64, 63], [65, 63], [65, 64], [66, 64], [66, 65], [67, 65], [67, 66], [68, 66],
                 [68, 67], [69, 67], [69, 68], [70, 68], [70, 69], [71, 69], [71, 70], [72, 70], [72, 71], [73, 71],
                 [73, 72], [74, 72], [74, 73], [75, 73], [75, 74], [76, 74], [76, 75], [77, 75], [77, 76], [78, 76],
                 [78, 77], [79, 77], [79, 78], [80, 78], [80, 79], [81, 79], [81, 80], [82, 80], [82, 81], [83, 81],
                 [83, 82], [84, 82], [84, 83], [85, 83], [85, 84], [86, 84], [86, 85], [87, 85]]
print(data.findOrder(numCourses, prerequisites))
numCourses = 3
prerequisites = [[0, 2], [1, 2], [2, 0]]
print(data.findOrder(numCourses, prerequisites))
